//
//  842. 将数组拆分成斐波那契序列.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/25.
//

import Foundation

//给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。
//
//形式上，斐波那契式 序列是一个非负整数列表 f，且满足：
//
//0 <= f[i] < 231 ，（也就是说，每个整数都符合 32 位 有符号整数类型）
//f.length >= 3
//对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]
//另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
//
//返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
//
//
//
//示例 1：
//
//输入：num = "1101111"
//输出：[11,0,11,11]
//解释：输出[110,1,111]也可以。
//示例 2：
//
//输入: num = "112358130"
//输出: []
//解释: 无法拆分。
//示例 3：
//
//输入："0123"
//输出：[]
//解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
//
//
//提示：
//
//1 <= num.length <= 200
//num 中只含有数字

// 回溯

func splitIntoFibonacci(_ num: String) -> [Int] {
    var res: [Int] = []
    let digits = Array(num)
    let _ = backtrack(digits, 0, &res)
    return res
}

func backtrack(_ digits: [Character], _ index: Int, _ res: inout [Int]) -> Bool {
    if index == digits.count && res.count >= 3 {
        return true
    }
    
    var num: Int64 = 0
    for i in index..<digits.count {
        if digits[index] == "0" && i > index {
            break
        }
        
        num = num * 10 + Int64(String(digits[i]))!
        if num > Int32.max {
            break
        }
        
        let count = res.count
        if count >= 2 && num > Int(res[count - 1]) + Int(res[count - 2]) {
            break
        }
        
        if count <= 1 || num == Int(res[count - 1]) + Int(res[count - 2]) {
            res.append(Int(num))
            if backtrack(digits, i + 1, &res) {
                return true
            }
            res.removeLast()
        }
    }
    
    return false
}

func 分割回文串11(_ s: String) -> [[String]] {
    var list = [Character](s)
    var item: [String] = []
    backStack(0, &list, &item)
    return ans
}

func backStack11(_ start: Int, _ list: inout [Character], _ itemList: inout [String]) {
    if start >= list.count {
        ans.append(itemList)
        return
    }
    for index in start..<list.count {
        let item = Array(list[start...index])
        // 常规判断回文的方式
        if !bValid(item) {
            continue
        }
        // 当前是回文
        itemList.append(String(item))
        backStack(index + 1, &list, &itemList)
        // 回溯
        itemList.removeLast()
    }
}

//常规的回文判断方法
func bValid11(_ s:[Character]) -> Bool {
    let len = s.count
    var left = 0,right = len - 1
    while left < right {
        if s[left] != s[right] {
            return false
        }
        left += 1
        right -= 1
    }
    return true
}
